package Year22_Month06.day23_博客;

public class 二叉树的最近公共祖先 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q) return root;//这一步是关键
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(left == null && right == null) return null;
        if(left == null) return right;
        if(right == null) return left;
        return root;
    }




//    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        //接下来就是进行判断
//        if(root == null) return null;
//        if(root == p || root == q) return root;//如果说p或者q任意一个为根节点，那祖先肯定是根节点
//        //如果说p q节点都在左侧，那就去左子树找祖先
//        if(find(root.left,p) && find(root.left,q)) return lowestCommonAncestor(root.left,p,q);
//        //如果说p q节点都在右侧，那就去右子树找祖先
//        if(find(root.right,p) && find(root.right,q)) return lowestCommonAncestor(root.right,p,q);
//        //如果不同时在一侧，那当前节点肯定就是祖先
//        return root;
//    }
//
//    public boolean find(TreeNode root,TreeNode target){
//        if(root == null) return false;
//        if(root == target) return true;
//        return find(root.left,target) || find(root.right,target);
//    }
}
